// Created by WXX on 2021/12/12 21:14
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <queue>

using namespace std;

// 因为 blocked 最大长度为 200, 两个点不连通当且仅当某个点被围住
// 围住的最多的点的个数为 m * (m - 1) / 2, 对应在某个角的三角形
/**
 * 执行用时：1016 ms, 在所有 C++ 提交中击败了11.60%的用户
 * 内存消耗：103.6 MB, 在所有 C++ 提交中击败了13.05%的用户
 */
class Solution {
public:
    unordered_set<string> S;
    int m, n = 1e6;

    string get(vector<int> p) {
        return to_string(p[0]) + ' ' + to_string(p[1]);
    }

    bool bfs(vector<int> source, vector<int> target) {

        auto st = S;
        queue<vector<int>> q;
        q.push(source);
        st.insert(get(source));

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        int cnt = 1;
        while (q.size()) {
            auto t = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int x = t[0] + dx[i], y = t[1] + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < n && !st.count(get({x, y}))) {
                    ++cnt;
                    if (cnt * 2 > m * (m - 1)) return true;
                    if (target[0] == x && target[1] == y) return true;

                    q.push({x, y});
                    st.insert(get({x, y}));
                }
            }
        }
        return false;
    }

    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        for (auto &b : blocked) S.insert(get(b));
        m = blocked.size();
        return bfs(source, target) && bfs(target, source);
    }
};

int main() {

    vector<vector<int>> blocked = {
            {0, 1},
            {1, 0}
    };
    vector<int> source = {0, 0}, target = {0, 2};
    cout << Solution().isEscapePossible(blocked, source, target) << endl;  // true

    return 0;
}
